#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct LinkNode{
	int data;
	struct LinkNode *next;
}*LinkNode,Node;
typedef struct{
	LinkNode front;
	LinkNode rear;
}LinkQueue;
typedef struct {
	LinkQueue *Q1;
	LinkQueue *Q2;
	int length;
	bool Q;
} MyStack;

void QueueInit(LinkQueue **Q){
	(*Q) = (LinkQueue*) malloc(sizeof(LinkQueue));
	(*Q)->front = NULL;
	(*Q)->rear = NULL;
}
bool IsEmpty(LinkQueue *Q){
	if(Q->front == NULL && Q->rear == NULL){
		return true;
	}
	return false;
}
void EnQueue(LinkQueue *Q,int data){
	LinkNode node = (LinkNode) malloc(sizeof(Node));
	node->data = data;
	if(IsEmpty(Q)){
		//说明这是第一个元素
		Q->rear = node;
		Q->front = node;
		return;
	}
	Q->rear->next = node;
	Q->rear = node;
}
void DeQueue(LinkQueue *Q,int *data){
	if(IsEmpty(Q)){
		printf("队列已空！\n");
		return;
	}
	*data = Q->front->data;
	LinkNode temp = Q->front;
	if(Q->front == Q->rear){
		//假如只剩一个元素
		Q->front  = NULL;
		Q->rear  = NULL;
		free(temp);
		return;
	}
	Q->front = temp->next;
	free(temp);
}
void QueueOutPut(LinkQueue *Q){
	LinkNode temp = Q->front;
	while (temp) {
		printf("%d\n",temp->data);
		temp = temp->next;
	}
}
MyStack* myStackCreate() {
	MyStack *s = (MyStack*) malloc(sizeof(MyStack));
	QueueInit(&(s->Q1));
	QueueInit(&(s->Q2));
	s->length = 0;
	s->Q = true;
	return s;
}

void myStackPush(MyStack* obj, int x) {
	if(obj->Q){
		EnQueue(obj->Q1, x);
	}
	else{
		EnQueue(obj->Q2, x);
	}
	obj->length++;
}
bool myStackEmpty(MyStack* obj) {
	if(obj->length == 0){
		return true;
	}
	return false;
}
int myStackPop(MyStack* obj) {
	//printf("length = %d",obj->length);
	int data;
	for (int i=0; i<obj->length; i++) {
		if(obj->Q){
			DeQueue(obj->Q1, &data);
			EnQueue(obj->Q2, data);
		}
		else{
			DeQueue(obj->Q2, &data);
			EnQueue(obj->Q1, data);
		}
		obj->Q = !obj->Q;
	}
	if(obj->Q){
		DeQueue(obj->Q1, &data);
	}
	else {
		DeQueue(obj->Q2, &data);
	}
	obj->length--;
	return data;
}

int myStackTop(MyStack* obj) {
	int data;
	for (int i=0; i<obj->length; i++) {
		if(obj->Q){
			DeQueue(obj->Q1, &data);
			EnQueue(obj->Q2, data);
		}
		else{
			DeQueue(obj->Q2, &data);
			EnQueue(obj->Q1, data);
		}
	}
	obj->Q = !obj->Q;
	return data;
}



void myStackFree(MyStack* obj) {
	int data;
	for (int i=0; i<obj->length; i++) {
		if(obj->Q){
			DeQueue(obj->Q1, &data);
			free(obj->Q1);
		}
		else{
			DeQueue(obj->Q2, &data);
			free(obj->Q2);
		}
		obj->Q = !obj->Q;
	}
	obj->Q1 = NULL;
	obj->Q2 = NULL;
//	free(obj);
}

/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);

* int param_2 = myStackPop(obj);

* int param_3 = myStackTop(obj);

* bool param_4 = myStackEmpty(obj);

* myStackFree(obj);
*/
int main(int argc, char *argv[]) {
	MyStack *s = myStackCreate();
	int choose;
	printf("1.入栈 2.出栈 3.获取栈顶元素:");
	while(scanf("%d",&choose)!=EOF && choose!=-1){
		if(choose == 1){
			int data;
			printf("输入入栈元素:");
			scanf("%d",&data);
			myStackPush(s, data);
		}
		else if(choose == 2) {
				printf("出栈元素为:%d\n",myStackPop(s));
		}
		else if(choose == 3) {
//			if(GetTop(stack, x)){
				printf("栈顶元素为:%d\n",myStackTop(s));
//			}
//			else {
//				printf("操作失败！栈已空！\n");
//			}
		}
		else if(choose == 4){
			if(myStackEmpty(s)){
				printf("empty\n");
			}
			else{
				printf("no");
			}
		}
		else{
			myStackFree(s);
		}
		printf("1.入栈 2.出栈 3.获取栈顶元素:");
	}
}